const COINS: [u32; 8] = [1, 2, 5, 10, 20, 30, 50, 100];  // 可用的硬币面额
// 该函数使用动态规划（DP）算法计算组成指定金额amount所需的最少硬币数。
// 首先初始化一个dp数组，其中dp[i]表示组成金额i所需的最少硬币数。初始时，dp[0]为0（表示0元需要0个硬币），其余金额初始化为最大值，表示无法组成。
// 通过迭代每个金额i，对所有硬币面额尝试更新dp[i]，如果使用当前硬币能够减少硬币数，则更新最小值。
// 最终，dp[amount]即为组成指定金额所需的最少硬币数。如果dp[amount]仍为最大值，则说明无法用给定的硬币面额组成该金额。
pub fn dp_rec_mc(amount: u32) -> u32 {
    // dp[i] 表示组成金额i所需的最少硬币数，初始化为最大值，表示无法组成
    let mut dp = vec![u32::MAX; (amount + 1) as usize];
    dp[0] = 0;  // 零元的情况下，硬币数为0

    // 从1到amount，依次计算每个金额所需的最少硬币数
    for i in 1..=amount {
        // 遍历所有硬币面额
        for &coin in &COINS {
            if i >= coin {
                // 如果当前金额i大于等于硬币面额coin，则尝试用coin来更新dp[i]
                dp[i as usize] = dp[i as usize].min(dp[(i - coin) as usize] + 1);
                // 这里dp[(i - coin)] + 1表示使用coin后，剩余金额i-coin所需的最少硬币数，再加上当前的coin
            }
        }
    }

    // 如果dp[amount]仍然为MAX，说明无法组成该金额
    dp[amount as usize]
}
